//
//  Permutations.swift
//  LeetCodeDemo
//
//  Created by Yangdongwu on 2020/12/19.
//

import Foundation

/*
 46. 全排列
 
 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 
 */

class Permutations {
    var res = [[Int]]()
    var temp = [Int]()
    var visited = [Bool]()
    
    func permute(_ nums: [Int]) -> [[Int]] {
        visited = [Bool](repeating: false, count: nums.count)
        backtrack(nums)
        return res
    }
    
    func backtrack(_ nums: [Int]) {
        if temp.count == nums.count {
            res.append(temp)
            return
        }
        for i in 0..<nums.count {
            if visited[i] {
                continue
            }
            temp.append(nums[i])
            visited[i] = true
            print("前:\(temp)")
            backtrack(nums)
            visited[i] = false
            temp.removeLast()
            print("后:\(temp)")
        }
    }
    
    
    func test() {
        print(permute([1,2,3]))
    }
}


class Permutations01 {
    
    var res = [[Int]]()
    var output = [Int]()
    
    func permute(_ nums: [Int]) -> [[Int]] {
        output = nums
        backtrack(output.count, 0)
        return res
    }
    
    func backtrack(_ n: Int, _ first: Int) {
        if first == n {
            res.append(output)
        }
        for i in first..<n {
            output.swapAt(first, i)
            print("前:\(output)")
            backtrack(n, first + 1)
            output.swapAt(first, i)
            print("后:\(output)")
        }
    }
    
    func test() {
        permute([1,2,3])
    }
    
}

